package com.gitee.ywj1352.算法.week01;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * <p>
 * }
 * <p>
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * <p>
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */

public class MergeTwoLists {

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //标记头
        ListNode pl = new ListNode(-1);
        //当前标识
        ListNode prev = pl;
        while (l1!=null && l2!=null){
           if (l1.val < l2.val){
               prev.next = l1;
               l1 = l1.next;
           }else {
               prev.next = l2;
               l2 = l2.next;

           }
           prev = prev.next;
        }

        if (l1!=null) prev.next = l1;
        if (l2!=null) prev.next = l2;
        return pl.next;
    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode pl  = new ListNode(-1),pre;
        pre = pl;

        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                pre.next = new ListNode(l1.val);
                l1 = l1.next;
            }else {
                pre.next =  new ListNode(l2.val);
                l2 = l2.next;
            }
            pre = pre.next;

        }
        return pl.next;
    }


    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * [1,2,4]
     * [1,3,4]
     * @param args
     */
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(4);

        ListNode k1 = new ListNode(2);
        ListNode k2 = new ListNode(3);
        ListNode k3 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;

        k1.next = k2;
        k2.next = k3;
        ListNode listNode = mergeTwoLists2(l1, k1);
        System.out.println(listNode);
    }
}
